#ifndef _DIJKSTRA_
#define _DIJKSTRA_

#include "graphe.hpp"
#include "file_priorite.hpp"


// tableau pour la distance entre les noeuds

struct item_dist {
    Noeud* destination;
    int distance;
};

struct tab_dist {
    int nb_items;
    int capa_items;
    item_dist** contenu;
};

// Tableau pour les noeuds précedents

struct item_prev {
    Noeud* actuel;
    Noeud* precedent;
};

struct tab_prev {
    int nb_items;
    int capa_items;
    item_prev** contenu;
};

// Fonctions pour tab_dist
tab_dist* initTabDist(bool verbose = false);
/*  précondition : aucune
    postcondition : renvoie un pointeur sur une structure tab_dist
 */

void ajoutElemDist(tab_dist* tbd, Noeud *n, int dist);
/*  précondition : tbd et n initialisés
 *  postcondition : rajoute un élement à tbd contenant le pointeur n passé en
 *  param ainsi que la distance
 */

void modifDist(tab_dist* tbd, Noeud *n, int dist);
/*  précondition : tbd et n initialisés, n présent dans tbd
 *  postcondition : modifie la valeur de dist dans l'element de tbd contenant n
 */

int distanceNoeud(tab_dist* tbd, Noeud *n);
/*  précondition : tbd et n initialisés, n présent dans tbd
 *  postcondition : renvoie la valeur de la distance de l'élement contenant n
 */

void testamentTabDist(tab_dist* tbd);
/*  précondition : tbd initialisé
 *  postcondition : tbd ainsi que tous les élements qu'il contient libérés
 *
 */

// Fonctions pour tab_prev
tab_prev* initTabPrev(bool verbose = false);
/*  précondition : aucune
    postcondition : renvoie un pointeur sur une structure tab_prev
 */

void ajoutElemPrev(tab_prev* tbp, Noeud *actuel, Noeud *prev);
/*  précondition : tbp, actuel et prev initialisés
 *  postcondition : rajoute un élement à tbp contenant le pointeur actuel et
 *  le pointeur prev passés en paramètre
 */

void setElemPrev(tab_prev* tbp, Noeud *actuel, Noeud *prev);
/*  précondition : tab_prev, actuel et prev initialisés, actuel présent dans tbp
 *  postcondition : modifie la valeur de prev dans l'élement de tbp contenant
 *  actuel
 */

void testamentTabPrev(tab_prev* tbp);
/*  précondition : tbp initialisé
 *  postcondition : tbp ainsi que tous les élements qu'il contient libérés
 *
 */

/* ==============Calcul de Dijkstra============== */

void dijkstra_source(graphe* g, Noeud* source, bool verbose = false);
/*  précondition : g et source initialisés, source présent dans g
 *  postcondition : aucun changement sur g et source
 *  affiche le plus court chemin (ainsi que sa valeur) entre source et les
 *  autres noeuds de g
 */


#endif // _DIJKSTRA_
